package com.aynu.linkedList;

/**
 * @author mj
 * @version 1.0
 * @date 2020/12/1 0:01
 * 尤瑟夫问题
 */
public class Josepfu {
    public static void main(String[] args) {
        CircularSinglyList singlyList = new CircularSinglyList();
        //添加小孩
        singlyList.add(5);
        //遍历小孩
        singlyList.list();
        //小孩出圈的顺序
        singlyList.chu(2,1,5);
    }
}

class CircularSinglyList {
    //创建一个first节点
    private Boy first;
    //插入辅助指针
    private Boy curBoy;

    //添加节点
    public void add(int nums) {
        //判断小孩是否合法
        if (nums < 1) {
            System.out.println("数量不能小于1");
            return;
        }

        for (int i = 1; i <= nums; i++) {
            //创建一个boy
            Boy boy = new Boy();
            boy.num = i;
            //如果初次构建，则初始化数据,构造一个next指向自身的环形链表
            if (i == 1) {
                first = boy;
                curBoy = first;
                first.next = first;
            } else {
                //插入到环形链表
                curBoy.next = boy;
                boy.next = first;
                curBoy = boy;
            }
        }
    }

    //遍历节点
    public void list() {
        //定义一个辅助指针
        curBoy = first;
        while (true) {
            //自己的
            //判断是否到头了，通过判断下一个节点是否是first节点，来判断是否链表到头
            /*if (curBoy.next == first) {
                if (curBoy != first) {
                    //打印是第几个小孩
                    System.out.printf("第%d个小孩\n", curBoy.num);
                }
                return;

            } else {
                //打印是第几个小孩
                System.out.printf("第%d个小孩\n", curBoy.num);
            }
            curBoy = curBoy.next;*/

            //老师的
            if (first == null) {
                return;
            }
            //考虑了输出边界的问题
            System.out.printf("第%d个小孩\n", curBoy.num);
            if (curBoy.next == first) {
                return;
            }
            curBoy = curBoy.next;
        }
    }

    /**
     * 出队列
     *
     * @param shuJiXia 数几下
     * @param startNo  从哪个小孩开始数
     * @param num      总共有几个小孩
     */
    public void chu(int shuJiXia, int startNo, int num) {
        if (shuJiXia<1||shuJiXia<1||num<1){
            System.out.println("输入参数有误！");
            return;
        }
        //创建辅助指针
        Boy helper = first;
        //循环链表使helper指向最后的节点
        for (int i = 1; i < num; i++) {
            helper = helper.next;
        }
        //然后让first指向，startNo
        for (int i = 1; i < startNo; i++) {
            first = first.next;
            helper = helper.next;
        }
        //每一个节点出队列
        while (true) {
            //当只有一个节点时，结束循环
            if (helper == first) {
                break;
            }
            //小孩数shuJiXia-1个数
            //当时first指向的是需要删除的节点
            for (int i = 0; i < shuJiXia - 1; i++) {
                first = first.next;
                helper = helper.next;
            }
            //输出出队列的节点
            System.out.printf("出队列，第%d个节点\n",first.num);
            //然后让first节点指向原来first节点指向的节点
            first = first.next;
            //然后让helper节点指向当前first节点，因为原理的fist节点没有应用，所以会被垃圾回收
            helper.next = first;
        }
        System.out.printf("在圈中的，第%d个节点\n",first.num);
    }
}

class Boy {
    public int num;
    public Boy next;
}
